Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Grüß Gott zusammen. Wir hatten letztes Mal gesehen, dass man mit dem C.G. Verfahren eigentlich ein

recht gutes Verfahren hat. Insofern, als es sich so verhält, also immer gemessen an diesem einen

Beispiel, wie weit das jetzt typisch ist, ist erstmal a priori schwer zu sagen, aber es ist

typisch ein Verfahren hat, das sich so verhält wie das SOR-Verfahren mit optimalen Relaxationsparameter.

Die Crux ist die, dass es eben von der Konditionszahl der Matrix abhängt und die ist für solche

Matrizen, wie sie aus der Diskretisierung von Differentialgleichungen entstehen, eben hoch.

Das heißt also, die allgemeine Frage ist, kann man denn nicht das Gleichungssystem so transformieren,

dass die Konditionszahl der Systemmatrix geringer wird, sodass damit das Verfahren effizienter wird.

Wir haben verschiedene Vorkonditionierungsansätze kennengelernt und da wir es ja mit symmetrischt

positiv definierten Problemen zu tun haben, was wir nicht durch die Vorkonditionierung kaputt

machen können, sind wir auf den sogenannten gesplitteten Ansatz gekommen. Das heißt,

wir brauchen wiederum eine symmetrische Vorkonditionierungsmatrix, die sich dann so

schreiben lässt, als W mal W transponiert. Das kann man sich als die Scholesky-Zerlegung

dieser Matrix vorstellen, die es ja immer gibt, wenn das C zum Beispiel auch positiv definiert ist.

Und wir haben gesehen, wenn wir jetzt mit dieser Matrix hier sozusagen von links und rechts

vorkonditionieren, dass wir einerseits mit dem W die Gleichung transformieren und analog auch

die Variable transformieren, dann bekommen wir ein transformiertes Problem, was Symmetrie und

Positivdefinite erhält und was aber genauso von der Kondition so dasteht, als wenn wir von links

oder von rechts mit einer Vorkonditionierungsmatrix multipliziert hätten. Jetzt natürlich jetzt die

Frage, wie findet man solche Vorkonditionierungsmatrizen und wir sind jetzt gekommen auf den Ansatz,

also erstmal, wie sieht das Verfahren aus und wir hatten dann festgestellt, das Verfahren,

was man bekommt, vielleicht gehe ich einfach nochmal auf das Verfahren, das heißt also man wende

das CG-Verfahren auf die transformierte Situation an, transformiere alles wieder zurück und schaue,

was dann passiert und dann entsteht ein Verfahren, was genauso aussieht wie das Original-CG-Verfahren,

mit dem kleinen Unterschied, dass hier an einer Stelle mal zusätzlich noch anstelle das hier

direkte Vektor GK plus eins, der K plus eine Gradient eingeht, ein Hilfsvektor eingeht,

der wir durch Lösen eines Gleichungssystems erhalten mit der Systemmatrix C. Das zeigt wiederum,

das C muss so gestaltet sein, dass das Auflösen eines linearen Gleichungssystems untergeordnet ist,

wenn das CE schon in Zerlegung da vorliegt, wie wir ja im Prinzip vorausgesetzt haben,

geht es bloß noch um Vorwärts-Rückwärts-Substitution und eigentlich sollte auch diese Vorwärts- und

Rückwärts-Substitution dann nur eine Komplexität groß O von N haben, wenn man es auf die dünn

besetzte Situation anwendet. Um jetzt das alles zu erfüllen für die Vorkonditionierung, also das

Problem ist nicht so sehr, das Verfahren dann zu implementieren, wenn man es einmal hat, das ist

eine minimale Änderung an der CG-Implementierung, das Problem ist eigentlich mehr die Vorkonditionierungsmatrix

zu finden. Wir sehen nochmal, was wir insgesamt dann haben, wir kennen diese Konvergenz-Ordnungsrate

mit dem Wurzel aus der Konditionszahl und jetzt ist eben die Konditionszahl nicht mehr die

Konditionszahl von A, sondern die hoffentlich kleinere und sozusagen systematisch kleinere

Konditionszahl von C hoch minus 1 mal A. Wie gesagt, ob wir hier C hoch minus 1 mal A oder A mal C oder

das gesplittete Situation anschauen, ist von der Konditionszahl das gleiche. So, diese Abschätzung

sagt jetzt, naja vielleicht wäre es ganz gut mal bei den stationären Iterationsverfahren zu schauen,

denn diese Abschätzung sagt, wenn ich als Konditionszahl sozusagen die Matrix hernehme,

die wir da in dem Kontext W genannt haben, bzw. der inverse N genannt worden ist, also die Matrix,

die dort das Hilfsgleichungssystem aufstellt, definiert, dass man lösen muss, um das Increment in

jedem Schritt aus dem negativen Residuum zu berechnen, dann sehen wir, wenn wir da ein

konvagentes Verfahren haben, dann bekommen wir eine sehr ordentliche Abschätzung für die Konditionszahl.

Also nehmen wir mal unsere alten Verfahren her, die sich als Verfahren an sich, sich für diesen

Typ von Problemen als nicht so gut erwiesen haben und jetzt ist halt die Problematik, jetzt brauchen

wir für dieses N eben eine symmetrischt positiv definierte Matrix unter der Voraussetzung,

dass die Ausgangsmatrix A symmetrisch positiv definiert ist.